from gurobipy import *
import numpy as np
from traffic_engineer import *
from traffic_engineering_class import *

class MultiClusterTESensitivityCriticalDemands(TrafficEngineer):
	## Takes in two new variables:
	## update_frequency - how much time in-between every traffic engineering events
	def __init__(self, aurora_network, all_interblock_paths, update_frequency, training_length, numK, reduce_multihop=False, sensitivity_relaxation=1, mlu_relaxation=1, return_predicted_mlu=False):
		TrafficEngineer.__init__(self, aurora_network, all_interblock_paths)
		assert(sensitivity_relaxation >= 1 and mlu_relaxation >= 1)
		self.sensitivity_relaxation = float(sensitivity_relaxation)
		self.mlu_relaxation = float(mlu_relaxation)
		self.update_frequency = update_frequency
		self.training_length = training_length
		self.reduce_multihop = reduce_multihop
		self.numK = numK
		self.return_predicted_mlu = return_predicted_mlu
		return

	def get_filename_param(self):
		#min_sensitivity_string = "{0:.6g}".format(self.minimum_sensitivity)
		#min_sensitivity_string = min_sensitivity_string.replace('.','p')
		return "rmtesenscrit_r{}t{}k{}".format(self.update_frequency, self.training_length, self.numK)
		return "rmtesensitive_minsense{}_r{}t{}k{}".format(min_sensitivity_string, self.update_frequency, self.training_length, self.numK)

	def get_num_clusters_for_training(self):
		return self.numK

	def get_string(self):
		return "Sensitivity Optimized for critical demands"

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.ROBUST_TE


	# given an MLU, find the topology/routing weights such that the average hop count in the worst case
	# is minimized. This is an LP formulation that directly minimizes hop count, rather than previously done
	# which is implicit through the use of QP to minimize non-minimal path weights
	def _minimize_multihop_direct(self, logical_topology_adj_matrix, traffic_matrices, worst_case_mlu, worst_case_critical_flow_sensivity):
		## using QP to reduce multihop reliance
		nblocks = self.aurora_network.get_num_blocks()
		num_tm = len(traffic_matrices)

		model = Model("minimize multihop directly")
		model.setParam( 'OutputFlag', False )
		routing_weights_var = {}
		direct_hopcount = model.addVar(lb=0, ub=1, obj=1., vtype=GRB.CONTINUOUS, name="max_ahc")
		link_capacity_constraints = [None] * num_tm
		for tm_index in range(num_tm):
			link_capacity_constraints[tm_index] = [None] * nblocks
			for i in range(nblocks):
				link_capacity_constraints[tm_index][i] = [None] * nblocks
				for j in range(nblocks):
					if i != j:
						link_capacity_constraints[tm_index][i][j] = LinExpr()

		## setup the link constraints and all optization variables, 
		## which are the link counts and routing variables
		for i in range(nblocks):
			for j in range(nblocks):
				if (i != j):
					routing_weight_sum = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weights_var[path] = model.addVar(lb=0, ub=GRB.INFINITY, obj=0., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						routing_weight_sum += routing_weights_var[path]
					model.addConstr(lhs=routing_weight_sum, sense=GRB.EQUAL, rhs=1)
		
		## add link capacity limit for all paths constraints
		for tm_index in range(num_tm):
			for i in range(nblocks):
				for j in range(nblocks):
					if (i != j):
						for path in self.all_interblock_paths[i][j]:
							path_len = len(path)
							curr_node = path[0]
							for next_node_index in range(1, path_len, 1):
								next_node = path[next_node_index]
								link_capacity_constraints[tm_index][curr_node][next_node] += (routing_weights_var[path] * traffic_matrices[tm_index][i][j])
								curr_node = next_node
		for tm_index in range(num_tm):
			for i in range(nblocks):
				for j in range(nblocks):
					if (i != j):
						capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
						model.addConstr(lhs=link_capacity_constraints[tm_index][i][j], sense=GRB.LESS_EQUAL, rhs=worst_case_mlu * logical_topology_adj_matrix[i][j] * capacity)

		## maximum average hop count constraint
		for tm_index in range(num_tm):
			traffic_matrix_ahc = LinExpr()
			traffic_sum = float(sum([sum(x) for x in traffic_matrices[tm_index]]))
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						traffic_matrix_ahc += (routing_weights_var[(i,j)] * (traffic_matrices[tm_index][i][j]/traffic_sum))
			if self.reduce_multihop:
				model.addConstr(lhs=direct_hopcount, sense=GRB.LESS_EQUAL, rhs=traffic_matrix_ahc)
			else:
				model.addConstr(lhs=traffic_matrix_ahc, sense=GRB.LESS_EQUAL, rhs=direct_hopcount)

		## also account for the sensitivity constraints
		## stage 3 : add the sensitivity constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					direct_path_capacity = logical_topology_adj_matrix[i][j]
					model.addConstr(lhs=routing_weights_var[(i, j)], sense=GRB.LESS_EQUAL, rhs=worst_case_critical_flow_sensivity * direct_path_capacity)
					for k in range(nblocks):
						if k != i and k != j:
							model.addConstr(lhs=routing_weights_var[(k, i, j)], sense=GRB.LESS_EQUAL, rhs=worst_case_critical_flow_sensivity * direct_path_capacity)
							model.addConstr(lhs=routing_weights_var[(i, j, k)], sense=GRB.LESS_EQUAL, rhs=worst_case_critical_flow_sensivity * direct_path_capacity)

		# set up the objective function
		if self.reduce_multihop:
			model.setObjective(direct_hopcount, GRB.MAXIMIZE)
		else:
			model.setObjective(direct_hopcount, GRB.MINIMIZE)
		# start optimizing
		routing_weights = {}
		try: 
			model.optimize()
			print("ave hop count after routing is : {}".format(2. - direct_hopcount.x))
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						for path in self.all_interblock_paths[i][j]:
							routing_weights[path] = routing_weights_var[path].x
			#print adj_matrix
		except GurobiError as e:
			print ("MinimizeMultihop Direct Robust Multi Traffic TE: Error code " + str(e. errno ) + ": " + str(e))
		except AttributeError :
			print ("MinimizeMultihop Direct Robust Multi Traffic TE: Encountered an attribute error ")
		return routing_weights

	# given an MLU, find the topology/routing weights such that the average hop count in the worst case
	# is minimized. This is an LP formulation that directly minimizes hop count, rather than previously done
	# which is implicit through the use of QP to minimize non-minimal path weights
	def _minimize_multihop_qp(self, logical_topology_adj_matrix, traffic_matrices, worst_case_mlu, worst_case_critical_flow_sensivity):
		## using QP to reduce multihop reliance
		nblocks = self.aurora_network.get_num_blocks()
		num_tm = len(traffic_matrices)
		print("Bleh Bleh worst case mlu is : {}".format(worst_case_mlu))
		model = Model("minimize multihop directly")
		model.setParam( 'OutputFlag', False )
		routing_weights_var = {}
		link_capacity_constraints = [None] * num_tm
		for tm_index in range(num_tm):
			link_capacity_constraints[tm_index] = [None] * nblocks
			for i in range(nblocks):
				link_capacity_constraints[tm_index][i] = [None] * nblocks
				for j in range(nblocks):
					if i != j:
						link_capacity_constraints[tm_index][i][j] = LinExpr()

		## setup the link constraints and all optization variables, 
		## which are the link counts and routing variables
		for i in range(nblocks):
			for j in range(nblocks):
				if (i != j):
					routing_weight_sum = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weights_var[path] = model.addVar(lb=0, ub=GRB.INFINITY, obj=0., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						routing_weight_sum += routing_weights_var[path]
					model.addConstr(lhs=routing_weight_sum, sense=GRB.EQUAL, rhs=1)
		
		## add link capacity limit for all paths constraints
		for tm_index in range(num_tm):
			for i in range(nblocks):
				for j in range(nblocks):
					if (i != j):
						for path in self.all_interblock_paths[i][j]:
							path_len = len(path)
							curr_node = path[0]
							for next_node_index in range(1, path_len, 1):
								next_node = path[next_node_index]
								link_capacity_constraints[tm_index][curr_node][next_node] += (routing_weights_var[path] * traffic_matrices[tm_index][i][j])
								curr_node = next_node
		for tm_index in range(num_tm):
			for i in range(nblocks):
				for j in range(nblocks):
					if (i != j):
						capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
						model.addConstr(lhs=link_capacity_constraints[tm_index][i][j], sense=GRB.LESS_EQUAL, rhs=worst_case_mlu * logical_topology_adj_matrix[i][j] * capacity)

		## also account for the sensitivity constraints
		## stage 3 : add the sensitivity constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					direct_path_capacity = logical_topology_adj_matrix[i][j]
					model.addConstr(lhs=routing_weights_var[(i, j)], sense=GRB.LESS_EQUAL, rhs=worst_case_critical_flow_sensivity * direct_path_capacity)
					for k in range(nblocks):
						if k != i and k != j:
							model.addConstr(lhs=routing_weights_var[(k, i, j)], sense=GRB.LESS_EQUAL, rhs=worst_case_critical_flow_sensivity * direct_path_capacity)
							model.addConstr(lhs=routing_weights_var[(i, j, k)], sense=GRB.LESS_EQUAL, rhs=worst_case_critical_flow_sensivity * direct_path_capacity)

		## maximum average hop count constraint
		qp_objective = QuadExpr()
		
		# set up the objective function
		if self.reduce_multihop:
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						for k in range(nblocks):
							if k != i and k != j:
								qp_objective += (routing_weights_var[(i,k,j)] * routing_weights_var[(i,k,j)])
		else:
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						qp_objective += (routing_weights_var[(i,j)] * routing_weights_var[(i,j)])
		model.setObjective(qp_objective, GRB.MINIMIZE)
		# start optimizing
		try: 
			routing_weights = {}
			model.optimize()
			#print("ave hop count after routing is : {}".format(2. - direct_hopcount.x))
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						routing_weights[(i, j)] = routing_weights_var[(i, j)].x
						weight_sum = routing_weights[(i, j)]
						for k in range(nblocks):
							if i != k and j != k:
								routing_weights[(i, k, j)] = routing_weights_var[(i, k, j)].x
								weight_sum += routing_weights[(i, k, j)]
						assert(abs(1-weight_sum) <= 0.00001)
			
			return routing_weights
		except GurobiError as e:
			print ("MinimizeMultihop Direct Robust Multi Traffic TE: Error code " + str(e. errno ) + ": " + str(e))
		except AttributeError :
			print ("MinimizeMultihop Direct Robust Multi Traffic TE: Encountered an attribute error ")
		return None

	#def _compute_mlu(self, traffic_matrices, capacity_matrix, all_paths):
	## Currently does not involve another step that reduces hop count
	def _compute_path_weights_minimize_worstcase_mlu(self, logical_topology_adj_matrix, traffic_matrices):
		nblocks = self.aurora_network.get_num_blocks()
		num_tm = len(traffic_matrices)
		model = Model("Routing minimize MLU for all traffic matrices")
		model.setParam( 'OutputFlag', False )
		mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=0, vtype=GRB.CONTINUOUS, name="mlu")
		routing_weight_vars = {}
		link_capacity_constraints = [None] * num_tm
		for k in range(num_tm):
			link_capacity_constraints[k] = [None] * nblocks
			for i in range(nblocks):
				link_capacity_constraints[k][i] = [None] * nblocks
				for j in range(nblocks):
					if i != j:
						link_capacity_constraints[k][i][j] = LinExpr()
						#routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=1., vtype=GRB.CONTINUOUS, name="w_{},{}".format(i,j))
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					weight_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0, ub=1., obj=1., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weight_constraint += routing_weight_vars[path]
					model.addConstr(lhs=weight_constraint, sense=GRB.EQUAL, rhs=1)


		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for tm, tm_index in zip(traffic_matrices, range(num_tm)):
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						for path in self.all_interblock_paths[i][j]:
							src = path[0]
							for path_hop in range(1, len(path), 1):
								dst = path[path_hop]
								link_capacity_constraints[tm_index][src][dst] += (routing_weight_vars[path] * tm[i][j])
								src = dst

		## stage 2 : add the link utilization constraints to the model
		for tm_index in range(num_tm):
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						lu_constraint = link_capacity_constraints[tm_index][i][j]
						capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
						model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=mlu * capacity * logical_topology_adj_matrix[i][j])

		# stage 3: set the objective
		model.setObjective(mlu, GRB.MINIMIZE)
		try: 
			model.optimize()
			routing_weights = {}
			print("Predicted MLU (TE) is : {}".format(mlu.x))
			for path in routing_weight_vars.keys():
				routing_weights[path] = routing_weight_vars[path].x
			return routing_weights, mlu.x
		except GurobiError as e:
			print ("Error code " + str(e. errno ) + ": " + str(e))
			return None
		except AttributeError :
			print ("Encountered an attribute error in Worst case MLU")
			return None

	def _minimize_max_sensitivity(self, logical_topology_adj_matrix, traffic_matrices, worst_case_mlu):
		routing_weights = {}
		nblocks = self.aurora_network.get_num_blocks()
		num_tm = len(traffic_matrices)
		model = Model("Desensitize")
		model.setParam( 'OutputFlag', False )
		routing_weight_vars = {}
		link_capacity_constraints = [None] * num_tm
		beta = model.addVar(lb=0., ub=GRB.INFINITY, obj=1, vtype=GRB.CONTINUOUS, name="beta")

		for k in range(num_tm):
			link_capacity_constraints[k] = [None] * nblocks
			for i in range(nblocks):
				link_capacity_constraints[k][i] = [None] * nblocks
				for j in range(nblocks):
					if i != j:
						link_capacity_constraints[k][i][j] = LinExpr()
		
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					weight_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=0, vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weight_constraint += routing_weight_vars[path]
					model.addConstr(lhs=weight_constraint, sense=GRB.EQUAL, rhs=1.)
		
		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for tm, tm_index in zip(traffic_matrices, range(len(traffic_matrices))):
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						for path in self.all_interblock_paths[i][j]:
							src = path[0]
							for path_hop in range(1, len(path), 1):
								dst = path[path_hop]
								link_capacity_constraints[tm_index][src][dst] += (routing_weight_vars[path] * tm[i][j])
								src = dst

		## stage 2 : add the link utilization constraints
		for tm_index in range(num_tm):
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						lu_constraint = link_capacity_constraints[tm_index][i][j]
						capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
						model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=worst_case_mlu * capacity * logical_topology_adj_matrix[i][j])
		
		## stage 3 : add the sensitivity constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					direct_path_capacity = logical_topology_adj_matrix[i][j]
					model.addConstr(lhs=routing_weight_vars[(i, j)], sense=GRB.LESS_EQUAL, rhs=beta * direct_path_capacity)
					for k in range(nblocks):
						if k != i and k != j:						
							model.addConstr(lhs=routing_weight_vars[(k, i, j)], sense=GRB.LESS_EQUAL, rhs=beta * direct_path_capacity)
							model.addConstr(lhs=routing_weight_vars[(i, j, k)], sense=GRB.LESS_EQUAL, rhs=beta * direct_path_capacity)
		model.setObjective(beta, GRB.MINIMIZE)
		try: 
			model.optimize()
			print("Minimum achievable max sensivity for after TE optimization is : {}".format(beta.x))
			routing_weights = {}
			for path in routing_weight_vars.keys():
				routing_weights[path] = routing_weight_vars[path].x
			return routing_weights, beta.x
		except GurobiError as e:
			print ("Error code " + str(e. errno ) + ": " + str(e))
			return None
		except AttributeError :
			print ("Encountered an attribute error ComputeMinimalSensitivity")
			return None

	def compute_path_weights(self, logical_topology_adj_matrix, traffic_matrices):
		## newly added for robustness
		#assert(self.numK == len(traffic_matrices))
		nblocks = self.aurora_network.get_num_blocks()
		#print(logical_topology_adj_matrix)
		_, worst_case_mlu = self._compute_path_weights_minimize_worstcase_mlu(logical_topology_adj_matrix, traffic_matrices)
		worst_case_mlu *= self.mlu_relaxation
		_, worst_case_sensivity = self._minimize_max_sensitivity(logical_topology_adj_matrix, traffic_matrices, worst_case_mlu)
		worst_case_sensivity *= self.sensitivity_relaxation
		##routing_weights = self._minimize_all_link_sensitivity(logical_topology_adj_matrix, traffic_matrices, worst_case_mlu, worst_case_sensivity)

		## now we need to determine what the largest sensitivity is
		#routing_weights = self._minimize_multihop_direct(logical_topology_adj_matrix, traffic_matrices, worst_case_mlu, worst_case_sensivity)
		routing_weights = self._minimize_multihop_qp(logical_topology_adj_matrix, traffic_matrices, worst_case_mlu, worst_case_sensivity)
		assert(routing_weights is not None)
		
		#routing_weights = self._minimize_all_sensitivity(logical_topology_adj_matrix, traffic_matrices, worst_case_mlu, max_tm)
		number_of_zero_indirect_weights = 0
		for path in routing_weights:
			if len(path) > 2 and routing_weights[path] == 0:
				number_of_zero_indirect_weights += 1
		print("The number of zero indirect weights : {}".format(number_of_zero_indirect_weights))
		if self.return_predicted_mlu:
			return routing_weights, worst_case_mlu
		else:
			return routing_weights















	'''
	def _minimize_all_link_sensitivity(self, logical_topology_adj_matrix, traffic_matrices, worst_case_mlu, max_sensitivity):
		routing_weights = {}
		nblocks = self.aurora_network.get_num_blocks()
		num_tm = len(traffic_matrices)
		model = Model("Desensitize")
		model.setParam( 'OutputFlag', False )
		routing_weight_vars = {}
		link_capacity_constraints = [None] * num_tm
		beta = model.addVar(lb=0., ub=GRB.INFINITY, obj=1, vtype=GRB.CONTINUOUS, name="beta")

		for k in range(num_tm):
			link_capacity_constraints[k] = [None] * nblocks
			for i in range(nblocks):
				link_capacity_constraints[k][i] = [None] * nblocks
				for j in range(nblocks):
					if i != j:
						link_capacity_constraints[k][i][j] = LinExpr()
		
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					weight_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=0, vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weight_constraint += routing_weight_vars[path]
					model.addConstr(lhs=weight_constraint, sense=GRB.EQUAL, rhs=1.)
		
		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for tm, tm_index in zip(traffic_matrices, range(len(traffic_matrices))):
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						for path in self.all_interblock_paths[i][j]:
							src = path[0]
							for path_hop in range(1, len(path), 1):
								dst = path[path_hop]
								link_capacity_constraints[tm_index][src][dst] += (routing_weight_vars[path] * tm[i][j])
								src = dst

		## stage 2 : add the link utilization constraints
		for tm_index in range(num_tm):
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						lu_constraint = link_capacity_constraints[tm_index][i][j]
						capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
						model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=worst_case_mlu * capacity * logical_topology_adj_matrix[i][j])
		
		## stage 3 : add the sensitivity constraints
		sum_sensitivity = QuadExpr()
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					direct_path_capacity = logical_topology_adj_matrix[i][j]
					if direct_path_capacity > 0:
						sum_sensitivity += (routing_weight_vars[(i, j)] * routing_weight_vars[(i, j)]) / (direct_path_capacity * direct_path_capacity)	
					model.addConstr(lhs=routing_weight_vars[(i, j)], sense=GRB.LESS_EQUAL, rhs=max_sensitivity * direct_path_capacity)
					for k in range(nblocks):
						if k != i and k != j:
							indirect_path_capacity = min(logical_topology_adj_matrix[i][k], logical_topology_adj_matrix[k][j])
							if indirect_path_capacity > 0:
								sum_sensitivity += (routing_weight_vars[(i, k, j)] * routing_weight_vars[(i, k, j)]) / (indirect_path_capacity * indirect_path_capacity)
							model.addConstr(lhs=routing_weight_vars[(i, k, j)], sense=GRB.LESS_EQUAL, rhs=max_sensitivity * indirect_path_capacity)
		model.setObjective(sum_sensitivity, GRB.MINIMIZE)

		try: 
			model.optimize()
			print("Minimum achievable sensivity for critical flows is : {}".format(beta.x))
			routing_weights = {}
			for path in routing_weight_vars.keys():
				routing_weights[path] = routing_weight_vars[path].x
			return routing_weights
		except GurobiError as e:
			print ("Error code " + str(e. errno ) + ": " + str(e))
			return None
		except AttributeError :
			print ("Encountered an attribute error ComputeMinimalSensitivity")
			return None

	'''


	'''
	## Given a topology and a routing solution, and a few traffic matrices, we want to find the critical flows, which
	## represent the traffic flows that contribute to the link which is at maximum utilization
	def _identify_critical_traffic_flows(self, logical_topology_adj_matrix, traffic_matrices, routing_weights, target_mlu):
		nblocks = self.aurora_network.get_num_blocks()
		critical_flows_set = set()
		for tm in traffic_matrices:
			link_utilization_matrix = np.zeros((nblocks, nblocks))
			for path in routing_weights:
				src = path[0]
				dst = path[-1]
				weight = routing_weights[path]
				if weight == 0:
					continue
				current_node = src
				for next_node in path[1:]:
					capacity = min(self.aurora_network.get_link_capacity(current_node), self.aurora_network.get_link_capacity(next_node))
					num_links = logical_topology_adj_matrix[current_node][next_node]
					if num_links == 0:
						break
					link_utilization_matrix[current_node][next_node] += (tm[src][dst] / (num_links * capacity))
					next_node = current_node
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j and link_utilization_matrix[i][j] / target_mlu >= 0.999:
						for k in range(nblocks):
							critical_flows_set.add((i,j))
							if k != i and k != j:
								critical_flows_set.add((i, k))
								critical_flows_set.add((k, j))
		# link sensitivity
		original_sensitivity = np.zeros((nblocks, nblocks))
		max_sensitivity = 0
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					sensitivity = routing_weights[(i,j)] / logical_topology_adj_matrix[i][j]
					for k in range(nblocks):
						if k != i and k != j:
							sensitivity = max(sensitivity, routing_weights[(i,j,k)] / logical_topology_adj_matrix[i][j])
							sensitivity = max(sensitivity, routing_weights[(k,i,j)] / logical_topology_adj_matrix[i][j])
					original_sensitivity[i][j] = sensitivity
					max_sensitivity = max(max_sensitivity, sensitivity)
		print("Original max sensitivity is : {}".format(max_sensitivity))

		print("Critical flows set {}".format(critical_flows_set))
		print("Fraction of critical flows to all flows: {}".format(float(len(critical_flows_set))/(nblocks * (nblocks - 1))))
		return critical_flows_set
	'''


